백준 20040번

오늘 풀어본 문제는 백준의 20040번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 5

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 $0$ 부터 $n − 1$ 까지 고유한 번호가 부여된 평면 상의 점 $n$ 개가 주어지며, 이 중 어느 세 점도 일직선 위에 놓이지 않는다. 매 차례 마다 플레이어는 두 점을 선택해서 이를 연결하는 선분을 긋는데, 이전에 그린 선분을 다시 그을 수는 없지만 이미 그린 다른 선분과 교차하는 것은 가능하다. 게임을 진행하다가 처음으로 사이클을 완성하는 순간 게임이 종료된다. 사이클 $C$ 는 플레이어가 그린 선분들의 부분집합으로, 다음 조건을 만족한다.

$C$ 에 속한 임의의 선분의 한 끝점에서 출발하여 모든 선분을 한 번씩만 지나서 출발점으로 되돌아올 수 있다.

문제는 선분을 여러 개 그리다 보면 사이클이 완성 되었는지의 여부를 판단하기 어려워 이미 사이클이 완성되었음에도 불구하고 게임을 계속 진행하게 될 수 있다는 것이다. 이 문제를 해결하기 위해서 게임의 진행 상황이 주어지면 몇 번째 차례에서 사이클이 완성되었는지, 혹은 아직 게임이 진행 중인지를 판단하는 프로그램을 작성하려 한다.

입력으로 점의 개수 $n$ 과 $m$ 번째 차례까지의 게임 진행 상황이 주어지면 사이클이 완성 되었는지를 판단하고, 완성되었다면 몇 번째 차례에서 처음으로 사이클이 완성된 것인지를 출력하는 프로그램을 작성하시오.

입력

입력은 표준입력을 사용한다. 입력의 첫 번째 줄에는 점의 개수를 나타내는 정수 $3 \le n \le 500,000$ 과 진행된 차례의 수를 나타내는 정수 $3 \le m \le 1,000,000$ 이 주어진다. 게임에서 사용하는 $n$ 개의 점에는 $0$ 부터 $n − 1$ 까지 고유한 번호가 부여되어 있으며, 이 중 어느 세 점도 일직선 위에 놓이지 않는다. 이어지는 $m$ 개의 입력 줄에는 각각 $i$ 번째 차례에 해당 플레이어가 선택한 두 점의 번호가 주어진다 $(1 \le i \le m)$ .

출력

출력은 표준출력을 사용한다. 입력으로 주어진 케이스에 대해, $m$ 번째 차례까지 게임을 진행한 상황에서 이미 게임이 종료되었다면 사이클이 처음으로 만들어진 차례의 번호를 양의 정수로 출력하고, $m$ 번의 차례를 모두 처리한 이후에도 종료되지 않았다면 $0$ 을 출력한다.

풀이과정

1, 2번째 시도

문제를 해결하기 위해 사용한 방식은 다음과 같다.

내가 만들어둔 분리 집합 자료구조인 DisjointSet 을 활용하여 연결해야 할 두 정점의 번호가 같은 집합에 있는지 확인한 뒤, 있다면 결과를 출력하고 프로그램을 종료하고, 없다면 병합을 진행한다.
사이클이 형성되지 않은 경우, $0$ 을 출력하고 프로그램을 종료한다.

코드는 다음과 같이 작성하였다. 두 번째 제출에서는 헤더파일의 코드를 붙여넣었다.

#include <bits/stdc++.h>
#include "disjoint_set.hpp"

using namespace std;

using ll = long long;
using ull = unsigned long long;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, m;
    cin >> n >> m;

    DisjointSet diset(n);
    bool success = false;

    for (int i=1; i<=m; i++) {
        int A, B;
        cin >> A >> B;

        if (diset.find(A) == diset.find(B)) {
            success = true;
            cout << i;
            break;
        }
        else {
            diset.merge(A, B);
        }
    }

    if (!success) {
        cout << 0;
    }

    return 0;
}

첫 번째 제출에서는 헤더파일의 내용을 포함하는 것을 깜빡하여 ‘컴파일 에러’가 떴고, 두 번째 제출에서는 제대로 붙여넣어, 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.

마무리

분리집합을 이용하는 간단한 문제였다. 역시 한 번 잘 만들어두니 계속해서 쓸 수 있는게 참 편리한 것 같다! 아쉬운 점은 깜빡하고 헤더 파일의 코드를 제출에 포함시키지 않는 실수를 했다는 것이다. 이런 실수를 다시 일으키지 않았으면 좋겠다.

참고로 내가 만든 DisjointSet 의 코드는 내 레포지토리²에서 확인할 수 있다.

오늘의 PS는 아직 끝나지 않았다!

1: https://www.acmicpc.net/problem/20040
2: https://github.com/ChoiCube84/baekjoon-solutions/blob/main/C%2B%2B/20040/disjoint_set.hpp

← Previous Post Next Post →